//
//  main.c
//  67. addBinary
//
//  Created by edz on 2020/7/9.
//  Copyright © 2020 edz. All rights reserved.
//


/*
 给你两个二进制字符串，返回它们的和（用二进制表示）。
 输入为 非空 字符串且只包含数字 1 和 0。

 示例 1:
 输入: a = "11", b = "1"
 输出: "100"
 
 示例 2:
 输入: a = "1010", b = "1011"
 输出: "10101"
  
 提示：
 每个字符串仅由字符 '0' 或 '1' 组成。
 1 <= a.length, b.length <= 10^4
 字符串如果不是 "0" ，就都不含前导零。
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


char * addBinary(char * a, char * b){
    int count = 0; // 进位
    int alen = (int)strlen(a);
    int blen = (int)strlen(b);
    int length = (alen > blen ? alen+1 : blen+1);
    char* result = malloc(sizeof(char) * length+1);
    result[length] = 0;
    
    while (alen - 1 >= 0 || blen - 1 >= 0 ) {
        int sum = count;
        sum += (alen - 1 >= 0? a[(alen - 1)]-'0':0);
        sum += (blen - 1 >= 0? b[(blen - 1)]-'0':0);
        count = sum/2;
        result[(length - 1)] = '0' + sum % 2;
        alen--;
        blen--;
        length--;
    }
    if (count == 0) {
        return result + 1;
    }
    
    result[0] = '1';
    return result;
    
}
